#include <cstdio>
#include <cstring>
#include <map>
#include <cstdlib>
#include <ctime>

using namespace std;

template <typename K, typename V>
class LRU {
public:
	LRU(int max_size)
		: m_max_size(max_size),
		  m_size(0),
		  m_head(NULL),
		  m_tail(NULL)
		{}

	~LRU() {
		Node* node = m_head;
		while (node) {
			Node* t_next = node->next;
			delete node;
			node = t_next;
		}
	}

	bool Get(const K& key, V& value) {
		if (m_hash.count(key)) {
			Node* node = m_hash[key];
			value = node->value;
			// move the current node to the head
			MoveToHead(node);
			return true;
		} else {
			return false;
		}
	}

	bool Insert(const K& key, K& value) {
		Node* node = NULL;
		if (m_hash.count(key)) {
			node = m_hash[key];
			MoveToHead(node);
			return false;
		} else {
			node = new Node();
			node->key = key;
			node->value = value;
			m_hash[key] = node;

			if (m_max_size == m_size) {
				Node* pre = m_tail->pre;
				m_hash.erase(m_tail->key);
				delete m_tail;
				m_tail = pre;
				if (pre) {
					pre->next = NULL;
				} else {
					m_tail = m_head = NULL;
				}
				--m_size;
			}
			if (m_head == NULL) {
				m_head = m_tail = node;
			} else {
				m_head->pre = node;
				node->next = m_head;
				m_head = node;
			}
			++m_size;
			return true;
		}
	}

	int size() const {
		return m_size;
	}

private:
	struct Node {
		K key;
		V value;
		Node* pre;
		Node* next;
		Node() : pre(NULL), next(NULL) {}
	};

	void MoveToHead(Node* node) {
		if (m_head != node) {
			if (node->next) {
				node->next->pre = node->pre;
				node->pre->next = node->next;
			} else {
				m_tail = m_tail->pre;
				m_tail->next = NULL;
			}
			m_head->pre = node;
			node->next = m_head;
			m_head = node;
		}
	}

	int m_max_size;
	int m_size;
	map<K, Node*> m_hash;
	Node* m_head, *m_tail;
};

int main() {
	LRU<int, int> lru(1000000);

	for (int i = 0; i < 10000000; ++i) {
		lru.Insert(rand() % 50000, i);
		//printf("size = %d\n", lru.size());
	}

	printf("size = %d\n", lru.size());

	return 0;
}
